import copy
import os
import random
import time

inputPath = './input/'
outputPath = './output/'
population = []
entites = []
Gnum = 0
Mnum = 0
# 请设置为偶数
length = 10
# 单个解最大迭代次数
trymax = 50
#   参考点
reference_point = [0,0]

#计算加工时长
def calculate_total_time(schedule):
    total_time = 0
    total_delay_time = 0
    delay_time = []
    for item in schedule:
        times = entites[item]['processing_time']
        curryTime = 0
        # 对于第一个工件直接相加
        if item == schedule[0]:
            for i in times:
                curryTime += i
                delay_time.append(curryTime)
        # 其他工件需要计算延迟时间
        else:
            for index, i in enumerate(times):
                # 第一个机器都会有延迟，直接加上延迟表中的第一项
                if index == 0:
                    # 更新当前时间
                    curryTime += delay_time[0] + i
                    # 更新延迟时间
                    delay_time[0] = curryTime
                else:
                    # 需要判断当前时间是否大于等于前一个工件的加工时间
                    if delay_time[index - 1] >= delay_time[index]:
                        curryTime += i
                        delay_time[index] = curryTime
                    # 否则需要加上上一个的等待时间
                    else:
                        # 时间差值
                        de = delay_time[index] - delay_time[index - 1]
                        curryTime = curryTime + de + i
                        delay_time[index] = curryTime
        # 计算延迟时间
        if delay_time[Mnum - 1] > entites[item]['delay']:
            total_delay_time += (delay_time[Mnum - 1] - entites[item]['delay'])
        # 计算总加工时间
        if delay_time[Mnum - 1] > total_time:
            total_time = delay_time[Mnum - 1]
    # print(total_time)
    return total_time, total_delay_time

# 读算例文件
def readFile(filename):
    global entites, Gnum, Mnum
    with open(filename, 'r') as file:
        # 工件个数
        Gnum = int(file.readline())
        # 机器个数
        Mnum = int(file.readline())
        file.readline()
        while True:
            flag = 0
            entity = {}
            for i in range(0, 3):
                line = file.readline()
                if not line:
                    flag = 1
                    break
                if i == 0:
                    continue
                if i == 1:
                    entity['delay'] = int(line.strip())
                if i == 2:
                    entity['processing_time'] = list(map(int, line.strip().split()))
            entites.append(entity)
            if flag == 1:
                break


maxA = 0
maxB = 0


# 单个解上限50次
# flag =  1 先淘汰被占有  适应值最小
# flag =  1 淘汰适应值最小

def init():
    global population,reference_point
    population = []
    random_numbers = list(range(Gnum))
    #  确定参考点
    maxX = 0
    maxY = 0
    for i in range(0, length):
        random.shuffle(random_numbers)
        result_array = random_numbers[:Gnum]
        item = {}
        item['array'] = result_array
        item_time = calculate_total_time(result_array)
        # 计算总加工时间
        item['process'] = int(item_time[0])
        # 计算总延迟时间
        item['delay'] = (item_time[1])

        if (item['process'] > maxX):
            maxX = item['process']
        if (item['delay'] > maxY):
            maxY = item['delay']

        # 计算适应值
        item['fit'] = 0
        # flag
        item['flag'] = 0
        population.append(item)
    reference_point[0] = maxX + 1000
    reference_point[1] = maxY + 1000
    fitness()


def I(x, y):
    area_x = (reference_point[0] - x[0]) * (reference_point[1] - x[1])
    area_y = (reference_point[0] - y[0]) * (reference_point[1] - y[1])
    if (x[0] <= y[0] and x[1] <= y[1]) or (y[0] <= x[0] and y[1] <= x[1]):
        return area_x - area_y
    else:
        intersection_width = max(min(reference_point[0] - x[0], reference_point[0] - y[0]), 0)
        intersection_height = max(min(reference_point[1] - x[1], reference_point[1] - y[1]), 0)
        intersection_area = intersection_width * intersection_height
        return area_x - intersection_area


# 计算种群的适应值
def fitness():
    for i, item in enumerate(population):
        fit = 0
        for j, item2 in enumerate(population):
            if i != j:
                x = (population[i]['process'], population[i]['delay'])
                y = (population[j]['process'], population[j]['delay'])
                fit += I(x, y)
        population[i]['fit'] = fit
        # print('fit = ',fit)   [a,b,c,d,e,f,g]


# 计算解x的标志位
def calFlag(x):
    for item in population:
        # x在两个目标上严格占优某解
        if item['process'] > x['process'] and item['delay'] > x['delay']:
            # 更新标志位
            x['flag'] = 0
            return True
    # 当前解x不好，没有任何占优
    x['flag'] = 1
    return False


# 随机交换原解中的num个位，得到新解
# num是随机数  ： (2-6)
def getNew(x):
    # print(x)
    num = random.randint(2,4)
    # print('随机数：', num)
    xTemp = copy.deepcopy(x)
    # 随机交换4个位置
    aa = random.sample(x['array'],num)
    if num == 2:
        xTemp['array'][aa[0]] = x['array'][aa[1]]
        xTemp['array'][aa[1]] = x['array'][aa[0]]
    # if num == 3:
    #     xTemp['array'][aa[0]] = x['array'][aa[2]]
    #     xTemp['array'][aa[1]] = x['array'][aa[1]]
    #     xTemp['array'][aa[2]] = x['array'][aa[0]]
    # if num == 4:
    #     xTemp['array'][aa[0]] = x['array'][aa[3]]
    #     xTemp['array'][aa[1]] = x['array'][aa[2]]
    #     xTemp['array'][aa[2]] = x['array'][aa[1]]
    #     xTemp['array'][aa[3]] = x['array'][aa[0]]
    # print(aa)

    # xTemp['array'][aa[2]] = x['array'][aa[1]]
    # xTemp['array'][aa[3]] = x['array'][aa[0]]
    item_time = calculate_total_time(xTemp['array'])

    # 计算总加工时间
    xTemp['process'] = int(item_time[0])
    # 计算总延迟时间
    xTemp['delay'] = (item_time[1])
    xTemp['fit'] = 0
    xTemp['flag'] = 0

    # 查询是否能放入？
    index = 0
    flag = calFlag(xTemp)
    while not flag:
        # print(index)
        index = index + 1
        if (index >= trymax):
            return False
        # 重新生成
        num = random.randint(2, 4)
        # print('随机数：',num)
        xTemp = copy.deepcopy(x)
        # 随机交换4个位置
        aa = random.sample(x['array'], num)
        if num == 2:
            xTemp['array'][aa[0]] = x['array'][aa[1]]
            xTemp['array'][aa[1]] = x['array'][aa[0]]
        if num == 3:
            xTemp['array'][aa[0]] = x['array'][aa[2]]
            xTemp['array'][aa[1]] = x['array'][aa[1]]
            xTemp['array'][aa[2]] = x['array'][aa[0]]
        if num == 4:
            xTemp['array'][aa[0]] = x['array'][aa[3]]
            xTemp['array'][aa[1]] = x['array'][aa[2]]
            xTemp['array'][aa[2]] = x['array'][aa[1]]
            xTemp['array'][aa[3]] = x['array'][aa[0]]

        item_time = calculate_total_time(xTemp['array'])

        # 计算总加工时间
        xTemp['process'] = int(item_time[0])
        # 计算总延迟时间
        xTemp['delay'] = (item_time[1])
        xTemp['fit'] = 0
        xTemp['flag'] = 0
        flag = calFlag(xTemp)
        # print(xTemp,flag,index)
    return xTemp

# 更新标志位
def flagUpdate():
    n = len(population)
    for i in range(0, n):
        for j in range(0, n):
            if i != j:
                # 有解在两个目标上严格占优自己
                if population[i]['process'] > population[j]['process'] and \
                        population[i]['delay'] > population[j]['delay']:
                    # 更新标志位
                    population[i]['flag'] = 1
                    break

# 通过两个解得出汉明距离
def hamming_path(array1, array2):
    array1 = copy.deepcopy(array1)
    array2 = copy.deepcopy(array2)
    path = [array1.copy()]
    n = len(array1)

    for correct_idx, target_value in enumerate(array2):
        if array1[correct_idx] != target_value:
            target_idx = array1.index(target_value)
            array1[correct_idx], array1[target_idx] = array1[target_idx], array1[correct_idx]
            path.append(array1.copy())
    return path
# 通过两个解得出汉明距离中部距离
def hamming_middle(a1,a2):
    path = hamming_path(a1['array'],a2['array'])[int(length / 2)]
    # 计算加工时间
    times = calculate_total_time(path)
    result = {}
    result['array'] = path
    result['process'] = times[0]
    result['delay'] = times[1]

    return result
# 汉明调整
def hamming_just():
    print("\n搜索算法结束，进入汉明优化")
    global population
    # 待删除的解
    after_delete = []
    new_population = []
    for index in range(0, int(length / 2)):
        # 通过两个解 得到汉明中路径
        newSol = hamming_middle(population[index * 2], population[index * 2 + 1])
        newSol['fit'] = 0
        newSol['flag'] = 0
        # 删除两个解中 较差的解
        # 先比较flag
        if population[index * 2]['flag'] == population[index * 2 + 1]['flag']:
            if population[index * 2]['fit'] < population[index * 2 + 1]['fit']:
                after_delete.append(index * 2)
                # new_population.append(index * 2 + 1)
            else:
                # new_population.append(index * 2)
                after_delete.append(index * 2 + 1)
        else:
            if population[index * 2]['flag'] == 1:
                # new_population.append(index * 2 + 1)
                after_delete.append(index * 2)
            else:
                after_delete.append(index * 2 + 1)
                # new_population.append(index * 2)
        # 添加新解到种群中
        new_population.append(newSol)

    # 开始删除
    new_population_a = [item for idx, item in enumerate(population) if idx not in after_delete]

    for item in new_population:
        new_population_a.append(item)

    population = copy.deepcopy(new_population_a)
    print(after_delete)
    for item in population:
        print(item)
# 领域搜索
def domainSearch(times):
    print()
    # for item in range(0, 3000):xz
    for item in range(0, times):
        print('\r', '已完成：', str(round(item / times * 100, 2)), '%', end="")
        # print('test_',len(population),'__',item % length)
        newX = getNew(population[item % length])

        # newX为False，说明该解的领域已经搜索50次以上了，采用下一个解
        if not newX:
            continue
        # 判断是否重复
        breakout = False
        for i in population:
            if newX['process'] == i['process'] and newX['delay'] == i['delay']:
                breakout = True
                break
        if breakout:
            continue

        fit = 0
        xnew = (newX['process'], newX['delay'])
        for it in population:
            y = (it['process'], it['delay'])
            fit += I(xnew, y)
        fitold = 0
        xold = (population[item % length]['process'], population[item % length]['delay'])
        for it in population:
            y = (it['process'], it['delay'])
            fitold += I(xold, y)
        # 判断是否比原来的解好
        if fit > fitold:
            del population[item % length]
            population.append(newX)
            fitness()

        flagUpdate()
    print("")
    for i in population:
        line = 'array = {},process = {}, delay = {}, fit = {}, flag = {}'.format(i['array'],i['process'], i['delay'], i['fit'], i['flag'])
        print(line)
def main(filename):
    print('数据集：',filename)
    global population,reference_point
    begin = time.time()
    readFile(inputPath + filename)
    init()

    flagUpdate()
    # 临域搜索次数
    ds_times = 3000000
    # 汉明优化次数
    hm_times = 3
    # 开始搜索
    for item in range(0,hm_times):
        print(f'\n第{item+1}次ds搜索')
        domainSearch(ds_times)
        print(f'\n第{item + 1}次hm搜索')
        hamming_just()
    domainSearch(ds_times)

    end = time.time()
    population = sorted(population, key=lambda x: x['fit'], reverse=True)
    for item in population:
        print(item['process'], item['delay'], item['fit'], item['flag'])
    print('运行时间：', round(end - begin, 2), 's')
    with open(outputPath + filename, 'w') as file:
        for i in population:
            line = 'array = {},process = {}, delay = {}, fit = {}, flag = {}'.format(i['array'],i['process'], i['delay'], i['fit'], i['flag'])
            file.write(line + '\n')



if __name__ == "__main__":
    for root, dirs, files in os.walk(inputPath):
        for file in files:
            # 初始化全局变量
            Mnum = 0
            Gnum = 0
            population = []
            reference_point = [0,0]
            entites = []
            file_name = file
            main(file_name)
